The size and number of maximum matchings in a network have found a largevariety of applications in many fields. As a ubiquitous property of diversereal systems, power-law degree distribution was shown to have a profoundinfluence on size of maximum matchings in scale-free networks, where the sizeof maximum matchings is small and a perfect matching often does not exist. Inthis paper, we study analytically the maximum matchings in two scale-freenetworks with identical degree sequence, and show that the first network has noperfect matchings, while the second one has many. For the first network, wedetermine explicitly the size of maximum matchings, and provide an exactrecursive solution for the number of maximum matchings. For the second one, wedesign an orientation and prove that it is Pfaffian, based on which we derive aclosed-form expression for the number of perfect matchings. Moreover, wedemonstrate that the entropy for perfect matchings is equal to thatcorresponding to the extended Sierpi\'nski graph with the same average degreeas both studied scale-free networks. Our results indicate that power-law degreedistribution alone is not sufficient to characterize the size and number ofmaximum matchings in scale-free networks.
展开▼
